#pragma once

#include <vector>
#include <utility>

namespace sorting
{
    /**
     * @brief       折半插入排序
     * @tparam  T   基本数据类型
     * @param   vec 基本数据类型的数组
     */
    template <typename T>
    void BinaryInsertionSort(std::vector<T> &vec)
    {
        using std::size_t;

        const size_t len = vec.size();
        if (len <= 1)
        {
            return;
        }

        for (size_t i = 1; i < len; ++i)
        {
            const T key = vec[i];
            size_t left = 0, right = i;

            // 寻找插入位置
            while (left < right)
            {
                const size_t mid = left + (right - left) / 2;
                if (vec[mid] > key)
                {
                    right = mid;
                }
                else
                {
                    left = mid + 1;
                }
            }

            // 移动元素，腾出插入位置
            for (size_t j = i; j > left; --j)
            {
                vec[j] = vec[j - 1];
            }
            vec[left] = key;
        }
    }
} // namespace sorting